/*
 * @lc app=leetcode.cn id=67 lang=c
 *
 * [67] 二进制求和
 */

// @lc code=start

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int ch2i(char v)
{
    return v - '0';
}
char i2ch(int v)
{
    return v + '0';
}

void reserve(char *s)
{
    // 高位与地位互换
    int len = strlen(s);
    for (int i = 0; i < len / 2; i++)
    {
        char t = s[i];
        s[i] = s[len - i - 1], s[len - i - 1] = t;
    }
}

char *addBinary(char *a, char *b)
{
    int len_a = strlen(a);
    int len_b = strlen(b);
    int to_next = 0;
    int max_len = fmax(len_a, len_b);
    // printf("max_len:%d\n", max_len);
    char *ret = (char *)malloc(sizeof(char) * (max_len + 2));
    int i;
    for (i = 0; i < max_len; i++)
    {
        int cur_a = i < len_a ? ch2i(a[len_a - i - 1]) : 0;
        int cur_b = i < len_b ? ch2i(b[len_b - i - 1]) : 0;
        // printf("p:%d, cur_a:%d, cur_b:%d\n", i, cur_a, cur_b);
        int total = (cur_a + cur_b + to_next);
        // printf("p:%d, total:%d, to_next:%d\n", i, total, to_next);
        // printf("c:%c\n", i2ch(total & 1));
        ret[i] = i2ch(total & 1);
        to_next = total >> 1;
        // printf("p:%d, value:%c, to_next:%d, total:%d\n", i, i2ch(total & 1), to_next, total);
    }
    if (to_next)
    {
        ret[i++] = '1';
    }
    ret[i] = '\0';
    // printf("total:%s\n", ret);
    reserve(ret);
    return ret;
}

// char *addBinary(char *a, char *b)
// {
//     reserve(a);
//     reserve(b);

//     int len_a = strlen(a), len_b = strlen(b);
//     int n = fmax(len_a, len_b), carry = 0, i = 0;
//     char *ans = (char *)malloc(sizeof(char) * (n + 2));
//     for (i = 0; i < n; ++i)
//     {
//         carry += i < len_a ? (a[i] == '1') : 0;
//         carry += i < len_b ? (b[i] == '1') : 0;
//         ans[i] = (carry & 1) + '0';
//         carry >>= 1;
//     }

//     if (carry)
//     {
//         ans[i++] = '1';
//     }
//     ans[i] = '\0';
//     reserve(ans);

//     return ans;
// }

int main()
{
    char a[] = "1101";
    char b[] = "100";
    char *result = addBinary(a, b);
    printf("total:%s\n", result);

    // Don't forget to free the allocated memory
    free(result);

    return 0;
}
// @lc code=end
